package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.ArrayList;

/**
 * Created by Administrator on 2017/4/17.
 * 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
 */
public class FindNumbersWithSum {
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Node> temp = new ArrayList<>();
        if (array == null || array.length <= 2) return result;
        int left = 0, right = array.length - 1;
        while (left < right) {
            int sumTemp = array[left] + array[right];
            if (sumTemp == sum) {
                temp.add(new Node(array[left++], array[right--]));
            } else if (sumTemp < sum) {
                left++;
            } else if (sumTemp > sum) {
                right--;
            }
        }
        int min = Integer.MAX_VALUE;
        int x = 0, y = 0;
        if (temp.isEmpty()) return result;
        for (Node node : temp) {
            if (node.left * node.right < min) {
                x = node.left;
                y = node.right;
                min=x*y;
            }
        }
        result.add(x);
        result.add(y);
        return result;
    }


    public static void main(String[] args) {
        FindNumbersWithSum findNumbersWithSum = new FindNumbersWithSum();
        ArrayList<Integer> integers = findNumbersWithSum.FindNumbersWithSum(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, 21);
        for (Integer integer : integers) {
            System.out.println(integer);
        }
    }

    private class Node {
        int left;
        int right;

        public Node(int left, int right) {
            this.right = right;
            this.left = left;
        }
    }
}
